#该算法只是将初始的随机取点进行了优化,kmeans++算法
import numpy
from matplotlib import pyplot
data=numpy.loadtxt('./testSet.txt')
length=len(data)
#先随机选出一个中心点
index=numpy.random.randint(length,size=1)
#再用kmeans++算法选出其他三个点
while len(index)<4:
    centre_point=data[index]
    shape=centre_point.shape
    distance2=numpy.empty((shape[0],length))
    p=numpy.empty(length)
    for j in range(shape[0]):
        for i in range(length):
            distance2[j,i]=numpy.sum((data[i]-centre_point[j])**2)
    distance=numpy.min(distance2,axis=0)
    sum=numpy.sum(distance)
    for i in range(length):
        p[i]=distance[i]/sum
    cump=numpy.cumsum(p)
    a=numpy.random.rand(1)
    if a[0]<=cump[0]:
        index=numpy.append(index,numpy.array([0]),axis=0)
    else:
        index = numpy.append(index, numpy.array([len(cump[cump<a])]), axis=0)
old_centre_point=data[index]
new_centre_point=old_centre_point.copy()
first=True
print(old_centre_point)
#选出初始中心点后，再进行迭代
while numpy.any(old_centre_point!=new_centre_point) or first==True:#当前后两次的中心点相同时停止循环,全为False时候才返回False
    old_centre_point = new_centre_point.copy()#记录上一次的值
    distance_class=numpy.empty((4,length))
    for j in range(4):
        for i in range(length):
            distance_class[j,i]=numpy.sqrt(numpy.sum((data[i]-old_centre_point[j])**2))
    class_index=numpy.argmin(distance_class,axis=0)
    dic_class={}
    for i in  range(4):
        dic_class[i]=data[class_index==i]
    #下面重新计算中心点
    for i in range(4):
        new_centre_point[i]=numpy.sum(dic_class[i],axis=0)/len(dic_class[i])
    #必须记录前后中心点的记录
    print(new_centre_point)
    pyplot.scatter(data[:, 0], data[:, 1], c=class_index)
    pyplot.scatter(old_centre_point[:, 0], old_centre_point[:, 1], c='red')#画出每次老的中心点
    pyplot.show()
    first=False
#收敛速度得到提升
